import java.util.Arrays;

/**
* @description: 600. 不含连续1的非负整数
* @author hewei
* @date 2022/8/16 14:47
* @version 1.0
*/

public class FindIntegers {

    char[] chars;
    int[] dp;
    public int findIntegers(int n) {
        chars = Integer.toBinaryString(n).toCharArray();
        dp = new int[chars.length];
        Arrays.fill(dp, -1);
        return dfs(0, false, true, false);
    }

    public int dfs(int i, boolean isNums, boolean isLimit, boolean isOne) {
        if (i == chars.length) return isNums ? 1 : 0;
        if (!isOne && !isLimit && isNums && dp[i] >= 0) return dp[i];

        int res = 0;
        if (!isNums) {
            res += dfs(i + 1, false, false, false);
        } else res += dfs(i + 1, true, isLimit && chars[i] == '0', false);
        if ((!isLimit || (chars[i] == '1')) && !isOne) res += dfs(i + 1, true, isLimit, true);
        if (!isOne && !isLimit && isNums) dp[i] = res;
        return res;
    }
}
